/*
 *  QueueList.h
 *
 *  Library implementing a generic, dynamic queue (linked list version).
 *
 *  ---
 *
 *  Copyright (C) 2010  Efstathios Xatzikiriakidis (efstxatzi@gmail.com)
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 *  ---
 *
 *  Version 1.0
 *
 *    2010-09-28  Efstathios Xatzikiriakidis  <efstxatzi@gmail.com>
 *
 *      - added exit(), blink(): error reporting and handling methods.
 *
 *    2010-09-25  Alexander Brevig  <alexanderbrevig@gmail.com>
 *
 *      - added setPrinter(): indirectly reference a Serial object.
 *
 *    2010-09-20  Efstathios Xatzikiriakidis  <efstxatzi@gmail.com>
 *
 *      - initial release of the library.
 *
 *  ---
 *
 *  For the latest version see: http://www.arduino.cc/
 */

// header defining the interface of the source.
#ifndef _QUEUELIST2_H
#define _QUEUELIST2_H

// include necessary header for libraries.
#include <WProgram.h>


#include "Coordinate.h"

// the definition of the queue class.
template<class Coordinate>
class QueueList2 {
  public:
    // init the queue (constructor).
    QueueList2 ();

    // clear the queue (destructor).
    ~QueueList2 ();

    // push an item to the queue.
    void push (const Coordinate i);

    // pop an item from the queue.
    Coordinate pop ();

    // get an item from the queue.
    Coordinate peek () const;

    Coordinate getItem(int pos);

    void removeItem(Coordinate rItem);



    int indexOf(Coordinate item);

    // check if the queue is empty.
    bool isEmpty () const;

    // get the number of items in the queue.
    int count () const;

    // set the printer of the queue.
    void setPrinter (Print & p);

  private:
    // exit report method in case of error.
    void exit (const char * m) const;

    // led blinking method in case of error.
    void blink () const;

    // the pin number of the on-board led.
    static const int ledPin = 13;

    // the structure of each node in the list.
    typedef struct node {
      Coordinate item;      // the item in the node.
      node * next; // the next node in the list.
    } node;

    typedef node * link; // synonym for pointer to a node.

    Print * printer; // the printer of the queue.
    int size;        // the size of the queue.
    link head;       // the head of the list.
    link tail;       // the tail of the list.
};

// init the queue (constructor).
template<class Coordinate>
QueueList2<Coordinate>::QueueList2 () {
  size = 0;       // set the size of queue to zero.
  head = NULL;    // set the head of the list to point nowhere.
  tail = NULL;    // set the tail of the list to point nowhere.
  printer = NULL; // set the printer of queue to point nowhere.
}



// clear the queue (destructor).
template<class Coordinate>
QueueList2<Coordinate>::~QueueList2 () {
  // deallocate memory space of each node in the list.
  for (link t = head; t != NULL; head = t) {
    t = head->next; free (head);
  }

  size = 0;       // set the size of queue to zero.
  tail = NULL;    // set the tail of the list to point nowhere.
  printer = NULL; // set the printer of queue to point nowhere.
}

// push an item to the queue.
template<class Coordinate>
void QueueList2<Coordinate>::push (const Coordinate i) {
  // create a temporary pointer to tail.
  link t = tail;

  // create a new node for the tail.
  tail = (link) malloc (sizeof (node));

  // if there is a memory allocation error.
  if (tail == NULL)
    exit ("QUEUE: insufficient memory to create a new node.");

  // set the next of the new node.
  tail->next = NULL;

  // store the item to the new node.
  tail->item = i;

  // check if the queue is empty.
  if (isEmpty ())
    // make the new node the head of the list.
    head = tail;
  else
    // make the new node the tail of the list.
    t->next = tail;

  // increase the items.
  size++;
}

// pop an item from the queue.
template<class Coordinate>
Coordinate QueueList2<Coordinate>::pop () {
  // check if the queue is empty.
  if (isEmpty ())
    exit ("QUEUE: can't pop item from queue: queue is empty.");

  // get the item of the head node.
  const Coordinate item = head->item;

  // remove only the head node. //link is pointer of node
  link t = head->next; free (head); head = t;

  // decrease the items.
  size--;

  // return the item.
  return item;
}
template<class Coordinate>

Coordinate QueueList2<Coordinate>::getItem(int pos){
  int i;
  link thislink = head;
  if (isEmpty ())
    exit ("QUEUE: can't get item from queue: queue is empty.");

  if(pos==0){
   return head->item;
  }
  else{
  for(i=1;i<=pos;i++){
    //link nextLink = head->next;
    thislink = thislink->next;
  }
  return thislink->item;
  }

}
template<class Coordinate>
void QueueList2<Coordinate>::removeItem(Coordinate rItem){
link curLink;
curLink = head;
while(curLink->next!=NULL){
//if(((curLink->next))->item==rItem){
  if(rItem.isEqualTo((curLink->next)->item)){
  curLink->next = (curLink->next)->next;
}
else{
 curLink = curLink->next;
}
}
size--;
}

template<class Coordinate>
int QueueList2<Coordinate>::indexOf(Coordinate item){
int countIndex=0;
int i;
for(i=0;i<(this->count());i++){
 countIndex++;
//if(getItem(i)==item){
if(item.isEqualTo(getItem(i))){
 break;
}

}

return countIndex-1;
}
/*template<typename T>
void QueueList<T>::removeItem(T rItem){
link thislink = head;
int i
  if (isEmpty ())
    exit ("QUEUE: can't remove item from queue: queue is empty.");
  for(i=0;i<count;i++){


  }

}
*/
// get an item from the queue.
template<class Coordinate>
Coordinate QueueList2<Coordinate>::peek () const {
  // check if the queue is empty.
  if (isEmpty ())
    exit ("QUEUE: can't peek item from queue: queue is empty.");

  // return the item of the head node.
  return head->item;
}

// check if the queue is empty.
template<class Coordinate>
bool QueueList2<Coordinate>::isEmpty () const {
  return head == NULL;
}

// get the number of items in the queue.
template<class Coordinate>
int QueueList2<Coordinate>::count () const {
  return size;
}

// set the printer of the queue.
template<class Coordinate>
void QueueList2<Coordinate>::setPrinter (Print & p) {
  printer = &p;
}

// exit report method in case of error.
template<class Coordinate>
void QueueList2<Coordinate>::exit (const char * m) const {
  // print the message if there is a printer.
  if (printer)
    printer->println (m);

  // loop blinking until hardware reset.
  blink ();
}

// led blinking method in case of error.
template<class Coordinate>
void QueueList2<Coordinate>::blink () const {
  // set led pin as output.
  pinMode (ledPin, OUTPUT);

  // continue looping until hardware reset.
  while (true) {
    digitalWrite (ledPin, HIGH); // sets the LED on.
    delay (250);                 // pauses 1/4 of second.
    digitalWrite (ledPin, LOW);  // sets the LED off.
    delay (250);                 // pauses 1/4 of second.
  }

  // solution selected due to lack of exit() and assert().
}

#endif // _QUEUELIST_H

